Masala #0736
Graf ichidan to'plam
Sizga Grafning tugunlar soni \(N\) berilgan. Grafdagi tugunlar 1 dan N gacha nomerlangan. Grafda barcha \(u \% v == 0 (2 \le u, v \le n)\) shartni qanoatlantiradigan tugunlar orasida to’g’ridan to’g’ri yo’l mavjud. Siz quyidagi shartlarni qanoatlantiradigan to’plamni hosil qiling:
- To’plam elementlar soni imkon qadar kam bo’lsin
- Grafning barcha tuguni uchun quyidagi shartlardan biri bajarilsin:
- Tugun to’plam ichida mavjud bo’lsin
- Tugun bilan to’g’ridan to’g’ri yo’l mavjud bo’lgan boshqa bir tugun to’plam ichida mavjud bo’lsin
Kirish faylining dastlabki satrida bitta butun son, \(T (1 \le T \le 10^5)\) testlar soni kiritiladi.
Keyingi \(T\) ta qatorda bittadan butun son, \(N (1 \le N \le 10^6)\) graf tugunlar soni kiritiladi.
Chiqish faylida har bir test uchun alohida qatorda hosil qilingan to’plamning minimal uzunligi nechchi bo’lishini chop eting!
# | input.txt | output.txt |
---|---|---|
1 |
1 6 |
4 |
1-testda:
Grafda 2-4, 2-6, 3-6 yo’llar mavjud
To’plamni (1,4,5,6) qiymatlardan hosil qilsa bo’ladi.